const int N=5e6+10;
bool primes[N];

auto Init=[]
{
    primes[1]=true;
    for(int i=2;i<=N/i;++i)
    {
        if(!primes[i])
            for(int j=i*i;j<N;j+=i) primes[j]=true;
    }
    return 0;
}();

class Solution {
public:
    int countPrimes(int n) {
        int ans=0;
        for(int i=1;i<n;++i)
            if(!primes[i]) ++ans;
        return ans;
    }
};